package sword.offer;

import sword.offer.common.GenerateTree;
import sword.offer.common.Node;

import java.util.*;

/**
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
 * 链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class ThirtySix {

    public static void main(String[] args) {
        List<Integer> nodes = Arrays.asList(new Integer[]{4,2,5,1,3,null,6});
        Node node = GenerateTree.generateTree(nodes);
        Solution1 solution = new Solution1();
        solution.treeToDoublyList(node);
    }

    /**
     * 最直接的最简单的思路
     * 一颗二叉搜索树是排序树，我们最能联想到的就是将其按照线性顺序将每个结点拿出来，放到一个容器中
     * 然后再去构建一个双向队列
     * */
    static class Solution {
        List<Node> arrayList = new ArrayList<>();
        public Node treeToDoublyList(Node root) {
            if(root == null){
                return null;
            }
            recur(root);
            for (int i = 0; i < arrayList.size()-1; i++) {
                Node node = arrayList.get(i);
                Node nextNode = arrayList.get(i+1);
                node.right = nextNode;
                nextNode.left = node;
            }
            arrayList.get(0).left = arrayList.get(arrayList.size()-1);
            arrayList.get(arrayList.size()-1).right = arrayList.get(0);
            return arrayList.get(0);
        }

        public void recur(Node root){
            if(root == null){
                return;
            }
            recur(root.left);
            arrayList.add(root);
            recur(root.right);
        }
    }

    /**
     * 我们已经知道了中序遍历 可以将一颗二叉搜索树 按照其从小到大的结点进行访问<br />
     * 那我们就按照这个顺序将其串成一个双向链表不就好了吗？
     * 但是怎么串起来呢？我们需要借助一个pre指针，用来记录上次访问的结点。
     * */
    static class Solution1 {
        private Node head, pre;
        public Node treeToDoublyList(Node root) {
            if(root == null){
                return null;
            }
            recur(root);
            head.left = pre;
            pre.right = head;
            return head;
        }

        public void recur(Node cur){
            if(cur == null){
                return;
            }
            recur(cur.left);
            if(pre == null){
                head = cur;
            }else{
                pre.right = cur;
                cur.left = pre;
            }
            pre = cur;
            recur(cur.right);
        }
    }
}
